Leetcode 839

This question is marked hard, but in realality this is not a difficult question. Simple union find problem, you find all the samilar strs and union them , starts with n groups after union all possible strs, what you have left is group standing.

class Solution {
    // union find 
    int[] parent;
    int[] size;
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        parent = new int[n];
        size = new int[n];
        for(int i = 0; i < n; i ++){
            parent[i] = i;
            size[i] = 1;
        }
        int count = n;
        for(int i = 0; i < n; i ++){
            for(int j = i + 1; j < n; j ++){
                String a = strs[i];
                String b = strs[j];
                if(similar(a,b)){
                    count -= union(i,j);
                }
            }
        }
        return count;
    }
    private int find(int a){
        if(parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }
    private int union(int a, int b){
        int pa = find(a);
        int pb = find(b);
        if(pa == pb) return 0;
        if(size[pa] > size[pb]){
            // join b to a 
            parent[pb] = a;
            size[pa] += size[pb];
        }else{
            parent[pa] = b;
            size[pb] += size[pa];
        }
        return 1;
    }
    private boolean similar(String a, String b){
        int diff = 0;
        for(int i = 0; i < a.length(); i ++){
            if(a.charAt(i) != b.charAt(i)){
                diff ++;
            }
        }
        return diff == 2 || diff == 0;
    }
}